package org.yanse.algorithms.sort;

/**
 * 插入排序
 * 原理
 *     1.以最后一个元素temp与前面已经排好序的数组比较
 *     2.如果temp<当前元素 元素后移
 *     3.直到temp>=当前元素记录元素下标
 *     4.元素下标的元素赋值temp
 *     5.排序n-1次后排序完成
 */
public class InsertionSort {
    public static void sort(int[] arrays) {
        if (arrays == null || arrays.length == 0) {
            return;
        }

        int j;
        for (int i = 0; i < arrays.length - 1; i++) {
            int temp = arrays[i + 1];
            boolean flag = false;
            for (j = i; j >= 0 && arrays[j] > temp; j--) {
                arrays[j + 1] = arrays[j];
                flag = true;
            }
            if (flag) {
                arrays[j + 1] = temp;
            }
        }
    }
}
